package com.itheima.leetcode;

import java.util.LinkedList;

/**
 * 逆波兰表达式求值
 *
 * @FileName E02LeetCode150
 * @Description
 * @Author Sword
 * @date 2025-05-07
 **/
public class E02LeetCode150 {

    /*
        /   /
        /   /
        /   /
        /   /
        /   /
        -----

        1 + 2 中缀
        1 2 + 后缀
        "2","1","+,"3","*"

        遇到数字压入栈
        遇到运算符，就从栈弹出两个数字做运算，将结果压入栈
        遍历结束，栈中剩下的数字就是结果
     */
    public static int evalRPN(String[] tokens) {
        LinkedList<Integer> stack = new LinkedList<>();

        for (String token : tokens) {
            switch (token) {
                case "+" -> {
                    Integer b = stack.pop();
                    Integer a = stack.pop();
                    stack.push(a + b);
                }
                case "-" -> {
                    Integer b = stack.pop();
                    Integer a = stack.pop();
                    stack.push(a - b);
                }
                case "*" -> {
                    Integer b = stack.pop();
                    Integer a = stack.pop();
                    stack.push(a * b);
                }
                case "/" -> {
                    Integer b = stack.pop();
                    Integer a = stack.pop();
                    stack.push(a / b);
                }
                default -> {    //数字
                    stack.push(Integer.parseInt(token));
                }
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String[] tokens = {"2", "1", "+", "3", "*"};
        System.out.println(evalRPN(tokens));

        tokens = new String[]{"4", "13", "5", "/", "+"};
        System.out.println(evalRPN(tokens));

    }
}
